\documentclass{beamer}[10]

\usepackage{graphicx}
\usepackage{listings}

\definecolor{kugreen}{RGB}{50,93,61}
\definecolor{kugreenlys}{RGB}{132,158,139}
\definecolor{kugreenlyslys}{RGB}{173,190,177}
\definecolor{kugreenlyslyslys}{RGB}{214,223,216}

\mode<presentation> {
  \useoutertheme{default}
  \useoutertheme[hideothersubsections]{sidebar}
  \useinnertheme[shadow=true]{rounded}
  \useinnertheme{circles}
  \usecolortheme{orchid}
  \usecolortheme{whale}
  \usecolortheme[named=kugreen]{structure}

  \setbeamercolor*{frametitle}{parent=palette primary}
  \usefonttheme[onlymath]{serif}
  \setbeamerfont{block title}{size={}}
  
  \setbeamercovered{transparent}
  
  \logo{\includegraphics[width=1.2cm]{fudan.jpg}}
}

% \setbeamertemplate{blocks}[rounded][shadow=true]
  

\def\naive{na\"\i ve}
\def\Naive{Na\"\i ve}

\title[CoreDet]  % short title displayed in the bottom line
  {CoreDet: A Compiler and Runtime System for Deterministic
    Multithreaded Execution}
\author[Tom Bergan, etc.]{Tom Bergan \quad Owen Anderson \quad Joseph Devietti \quad
Luis Ceze \quad Dan Grossman}
\institute{University of Washington, Computer Science and Engineering}
\date{ASPLOS 2010}

\begin{document}

\begin{frame}
  \titlepage{}
  \begin{center}
      Presented by Wang Yuanxuan
  \end{center}
\end{frame}

\section{Introduction}

\subsection{Motivation}

\begin{frame}
  \frametitle{Motivation}
  \begin{itemize}
  \item<1-> \textbf{Nondeterminism} makes the development of multithreaded
    software substantially more difficult
  \item<2-> Suggest: minimize sources of software nondeterminism
  \item<3-> Parallelism is for performance and should not affect outputs
  \item<4-> What we want: \textbf{scalability} and
\textbf{performance} of multithreaded programming \&
\textbf{determinism} of sequential programming
  \end{itemize}
\end{frame}

\subsection{CoreDet Approach}

\begin{frame}
  \frametitle{CoreDet Approach}
  \begin{itemize}
  \item<1-> CoreDet: COmpiler and Runtime Environment that executes
    C/C++ programs DETerministically
  \item<2-> Do not need to save any information about find-grained
    memory interleavings
  \item<3-> Key aspect: Do not specify deterministic behavior we will produce
  \item<4-> \textit{What about debugging problems that only show in
      release version?}
  \item<5-> \Naive{} approach: Run one thread at a time, and switch
    threads deterministically
  \item<6-> Optimization: recovering parallelism when threads do not communicate
  \end{itemize}
  
\end{frame}

\subsection{Outline}

\begin{frame}
  \frametitle{Outline}
  \tableofcontents[hideallsubsections]
\end{frame}

\section{High-Level Approach}

\subsection{Starting Serial}
\begin{frame}
  \frametitle{Starting Serial}
  \begin{itemize}
  \item<1-> Serialize execution in a deterministic way
  \item<2-> Round-robin scheduling
  \item<3-> Each thread is scheduled for a \textbf{quantum}
  \item<4-> Compiler inserts code to count instruction numbers
  \end{itemize}
\end{frame}

\subsection{DMP-TM}
\begin{frame}
  \frametitle{DMP-TM}
  \begin{itemize}
  \item<1-> Conceptually simplest way: using \textcolor{red}{transactional memory}
    \begin{itemize}
    \item Implementation complexity
    \item STM has good performance only when TXs are small and most
      execution is outside transactions
    \item Quanta in CoreDet are not lexically scoped
    \end{itemize}
  \end{itemize}
\end{frame}

\subsection{Two-Stage Rounds}
\begin{frame}
  \frametitle{Two-Stage Rounds I}
  \begin{itemize}
  \item<1-> Three alternatives to avoid the need for speculation
  \item<2-> Divide each round into two
    \begin{itemize}
    \item Parallel mode: run in parallel, no communication
    \item Serial mode: schedule serially and allow arbitrarily communication
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Two-Stage Rounds II}
  \begin{figure}
    \centering
    \includegraphics[width=\textwidth]{figure1.png}
  \end{figure}
\end{frame}

\subsection{Three Alternatives}
\begin{frame}
  \frametitle{Three Alternatives}
  \begin{itemize}
  \item DMP-O: low overhead, poor scalability
  \item DMP-B: high overhead, good scalability
  \item DMP-PB: hybrid, middle ground overhead and scalability
  \end{itemize}
\end{frame}

\section{DMP-O: Ownership Tracking}

\subsection{Main Idea}
\begin{frame}
  \frametitle{Main Idea}
  \begin{itemize}
  \item<1-> Divide memory locations: \textit{thread-private} and \textit{may-be-shared}
  \item<2-> Thread can execute in parallel mode if it accesses only thread-private data
  \item<3-> It blocks at the first may-be-shared access
  \end{itemize}
\end{frame}

\subsection{Ownership Tracking}
\begin{frame}
  \frametitle{Ownership Tracking}
  \begin{itemize}
  \item<1-> Track ownership of memory locations at runtime
  \item<2-> Memory Ownership Table (MOT) maintains the ownership
    status of each location
  \item<3-> MOT changes occur only during serial mode
  \item<4-> Changes to the MOT are purely a matter of policy
  \end{itemize}
\end{frame}

\subsection{Nonblocking Shared Reads}
\begin{frame}
  \frametitle{Nonblocking Shared Reads}
  \begin{figure}
    \centering
    \includegraphics[height=0.8\textheight]{figure2.png}
  \end{figure}
\end{frame}

\subsection{The Length as Serial Mode}
\begin{frame}
  \frametitle{The Length as Serial Mode}
  \begin{itemize}
  \item Full serial mode: completely exhausts the quantum budget
  \item Reduced serial mode: ends serial mode immediately if a
    thread no longer holds any mutexes
  \end{itemize}
\end{frame}

\section{DMP-B: Store Buffering}

\subsection{Main Idea}
\begin{frame}
  \frametitle{Main Idea}
  \begin{itemize}
  \item<1-> All writes are entered directly into the private store buffer
  \item<2-> Each read first consult the store buffer, then shared-memory
  \item<3-> Commit mode after parallel mode for writes committing
  \item<4-> Determinism in both modes
  \item<5-> Two restrictions for correctness
    \begin{enumerate}
    \item Parallel mode must end once a memory fence is reached
    \item Atomic operations like CAS cannot execute in parallel mode
    \end{enumerate}
  \end{itemize}
\end{frame}

\subsection{DMP-B Timeline}
\begin{frame}
  \frametitle{DMP-B Timeline}
  \includegraphics[width=\textwidth]{figure3.png}
\end{frame}  

\subsection{Memory Consistency Model}
\begin{frame}
  \frametitle{Memory Consistency Model I}
  \begin{figure}
    \centering
    \includegraphics[height=0.8\textheight]{figure4.png}
  \end{figure}
\end{frame}

\begin{frame}
  \frametitle{Memory Consistency Model II}
  \begin{itemize}
  \item<1-> DMP-B improves scalability by relaxing memory ordering
  \item<2-> Not sequentially consistent
  \item<3-> Does not violate the semantics of the original program
  \end{itemize}
\end{frame}

\subsection{Determinism Parallel Commit}
\begin{frame}
  \frametitle{Deterministic Parallel Commit}
  \begin{enumerate}
  \item<1-> Allow store buffers to commit in any order
  \item<2-> Byte-level metadata to enforce the commit order
  \item<3-> Locks chunks before publishing, which incurs heavy overheads
  \end{enumerate}
\end{frame}

\section{DMP-PB: Partial Buffer}

\subsection{Hybrid Scheme}
\begin{frame}
  \frametitle{Hybrid Scheme}
  \begin{itemize}
  \item MOT to partition the address space into private and shared data
  \item Extend the MOT to support \textit{always-shared} state
  \end{itemize}
\end{frame}

\section{Compiler Transformations}

\subsection{Compiler Instruments}
\begin{frame}
  \frametitle{Compiler Instruments}
  \begin{itemize}
  \item<1-> Additional pass in the LLVM
  \item<2-> Instruments loads and stores with \textit{CDload[T], CDstore[T]}
  \item<3-> Count work dynamically by setting the \textit{i} parameter in CDcommit(\textit{i})
  \item<4-> CDcommit(\textit{i}) subtracts \textit{i} from a
    thread-local counter and ends the quantum if it reaches 0
  \end{itemize}
\end{frame}

\subsection{Balanced Quantum}
\begin{frame}
  \frametitle{Balanced Quantum}
  \begin{block}{Maximal Balance}
    Call CDcommit(\textit{i}) at
    \begin{itemize}
    \item At the end of basic block B if its successor has multiple predecessors
    \item Before every function call and function return
    \end{itemize}
  \end{block}

  \begin{block}{Minimal Balance}
    Call CDcommit(\textit{i}) before every backedge and function call
  \end{block}

  \begin{block}{Heuristic Balance}
    Call CDcommit(\textit{i}) in a hybrid and heuristic way
  \end{block}
\end{frame}

\section{Evaluation}

\subsection{Scalability}
\begin{frame}
  \frametitle{Scalability}
  \begin{overprint}
    \onslide<1>
    \begin{figure}
      \centering
      \includegraphics[height=.6\textheight]{scale1.png}
    \end{figure}

    \onslide<2>
    \begin{figure}
      \centering
      \includegraphics[height=.6\textheight]{scale2.png}
    \end{figure}
  \end{overprint}
\end{frame}

\subsection{Overhead}
\begin{frame}
  \frametitle{Overhead}
  \begin{overprint}
    \onslide<1>
    \begin{figure}
      \centering
      \includegraphics[height=.6\textheight]{overhead1.png}
    \end{figure}

    \onslide<2>
    \begin{figure}
      \centering
      \includegraphics[height=.6\textheight]{overhead2.png}
    \end{figure}
  \end{overprint}
\end{frame}

\subsection{Sensitivity}
\begin{frame}
  \frametitle{Sensitivity}
  \begin{block}{streamcluster sensitivity for DMP-O}
    \begin{figure}
      \centering
      \includegraphics[height=.7\textheight]{sensitivity.png}
    \end{figure}
  \end{block}
\end{frame}

\section{Conclusions}

\subsection{CoreDet}
\begin{frame}
  \frametitle{CoreDet}
  \begin{itemize}
  \item A fully automatic compiler and runtime system for
    deterministic execution 
  \item Two basic approaches to enforcing determinism
    \begin{enumerate}
    \item Ownership tracking
    \item Memory versioning
    \end{enumerate}
  \end{itemize}
\end{frame}

\end{document}
